//在考场里，一排有 N 个座位，分别编号为 0, 1, 2, ..., N-1 。 
//
// 当学生进入考场后，他必须坐在能够使他与离他最近的人之间的距离达到最大化的座位上。如果有多个这样的座位，他会坐在编号最小的座位上。(另外，如果考场里没有人，
//那么学生就坐在 0 号座位上。) 
//
// 返回 ExamRoom(int N) 类，它有两个公开的函数：其中，函数 ExamRoom.seat() 会返回一个 int （整型数据），代表学生坐的位
//置；函数 ExamRoom.leave(int p) 代表坐在座位 p 上的学生现在离开了考场。每次调用 ExamRoom.leave(p) 时都保证有学生坐在
//座位 p 上。 
//
// 
//
// 示例： 
//
// 输入：["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[]
//,[4],[]]
//输出：[null,0,9,4,2,null,5]
//解释：
//ExamRoom(10) -> null
//seat() -> 0，没有人在考场里，那么学生坐在 0 号座位上。
//seat() -> 9，学生最后坐在 9 号座位上。
//seat() -> 4，学生最后坐在 4 号座位上。
//seat() -> 2，学生最后坐在 2 号座位上。
//leave(4) -> null
//seat() -> 5，学生最后坐在 5 号座位上。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= N <= 10^9 
// 在所有的测试样例中 ExamRoom.seat() 和 ExamRoom.leave() 最多被调用 10^4 次。 
// 保证在调用 ExamRoom.leave(p) 时有学生正坐在座位 p 上。 
// 
// Related Topics 设计 有序集合 
// 👍 94 👎 0

  
package com.zwy.leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zwy 
 */
public class ExamRoom{
    public static void main(String[] args) {
//        Solution solution = new ExamRoom().new Solution();
        ExamRoom0 s=new ExamRoom().new ExamRoom0(10);
        int seat1 = s.seat();
        int seat2 = s.seat();
        int seat3 = s.seat();
        int seat4 = s.seat();
        s.leave(4);;
        int seat5 = s.seat();
      }
     
/**
 *时间复杂度为:
 * @author zwy 
 */ 
      //leetcode submit region begin(Prohibit modification and deletion)
class ExamRoom0 {
    private int n;
    private int []arr=null;
    private int start=0;
    public ExamRoom0(int n) {
        this.n=n;
        arr=new int[n];
    }
    
    public int seat() {
        int min=Integer.MAX_VALUE;
        int last=0;
        int t=0;
        boolean flag=false;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]==1&&!flag){
                flag=true;
                last=i;
                continue;
            }
            if(arr[i]==1){
                t=i-last;
                if(t%2!=0){
                    t=t-1;
                }
               if(t<min){
                   start=i-t-1;
               }
            }
        }
        if(!flag){
            arr[0]=1;
            return 0;
        }
        arr[start]=1;
        return start;
    }
    
    public void leave(int p) {
        arr[p]=0;
    }
}

/**
 * Your ExamRoom object will be instantiated and called as such:
 * ExamRoom obj = new ExamRoom(n);
 * int param_1 = obj.seat();
 * obj.leave(p);
 */
//leetcode submit region end(Prohibit modification and deletion)

}